package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/5/31 20:47
 * @description:
 */
public class FindGreatestSumOfSubArray42 {

    //通过指针，枚举方式 比较有技巧
    public int FindGreatestSumOfSubArray(int[] array) {
        //双指针
        if (array==null || array.length==0){
            return 0;
        }
        if(array.length==1){
            return array[0];
        }

        //累加求和
        int sum [] = new int [array.length];
        sum[0] = array[0];
        for (int i=1; i<array.length;i++){
            sum[i] = sum[i-1]+array[i];
        }

        //双指针
        int max =sum[0];
        for(int i=0;i<array.length;i++){
            for(int j=0;j<=i;j++){
                if(j==0){
                    max = Math.max(max, sum[i]); //从0开始累加
                }else{
                    max = Math.max(max, sum[i]-sum[j-1]); //从j到i的累加值就是sum[i]-sum[j-1]
                }
            }
        }
        return max;
    }

    //动态规划问题
    public int FindGreatestSumOfSubArray1(int[] array) {
        if (array==null || array.length==0){
            return 0;
        }
        if(array.length==1){
            return array[0];
        }
        int max = array[0];
        int [] dp = new int[array.length];
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(array[i], dp[i-1]+array[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

}
